#include<stdio.h>
#include<algorithm>
using namespace std;

struct rectangle//记录小矩形的各个数据
{//横竖坐标、宽、高
    long long int l,t,w,h;
}rtg[10000];//小矩形数组

struct cmp
{//矩形越左排位越前
    bool operator()(rectangle &r1,rectangle &r2)
    {
        return r1.l<r2.l;
    }
};
//数据量大，开long long
//大矩形坐标R
//当前解x=ans左边小矩形的面积left_area
//所有小矩形总面积sum_area
//答案ans
long long int R,left_area=0,sum_area=0,ans;
int N;//小矩形数目
//求x=k左侧小矩形的总面积
long long int sum(long long int k)
{
    long long int sum=0;
    for(int i=0;i<N;i++)
    {
        if(rtg[i].l+rtg[i].w<=k)
           sum+=rtg[i].w*rtg[i].h;
        else if(rtg[i].l<k && rtg[i].l+rtg[i].w>k)
           sum+=(k-rtg[i].l)*rtg[i].h;
        else break;//已经按"越左越前"排过序，可以直接退出
    }
    return sum;
}

int main()
{
    scanf("%lld%d",&R,&N);
    for(int i=0;i<N;i++)
    {
        scanf("%lld%lld%lld%lld",&rtg[i].l,&rtg[i].t,&rtg[i].w,&rtg[i].h);
        //顺便计算所有小矩形面积和sun_area
        //因为之后要比较两次搜索左边小矩形面积和的大小，
        //所以给left_area赋初值为最大值
        left_area=sum_area+=rtg[i].w*rtg[i].h;
    }
    sort(rtg,rtg+N,cmp());//排序
    //x=mid左边的小矩形总面积temp_left
    //左开右开区间(0,R+1)，解绝对不可能是0、R+1
    long long int left=0,right=R+1,mid,temp_left;
    while(left+1!=right)//左开右开对应的结束边界
    {   //因为要找最后一个元素，故mid不妨向上取整
        mid=left+((right-left+1)>>1);
        temp_left=sum(mid);
        if(2*temp_left==sum_area){
            ans=mid;
            left_area=temp_left;
            //因为要找最后一个，所以在(mid,right)继续搜索
            left=mid;
        }
        else if(2*temp_left>sum_area){
            //找到更小面积差的位置，则记录答案
            if(temp_left<left_area){
                ans=mid;
                left_area=temp_left;
            }
            //左边大了，区间左移，排除mid，区间变为(left,mid)
            right=mid;
        }
        //左边太小，区间右移，排除mid，区间变为(mid,right)
        else left=mid;
    }
    //保险起见，检验找到元素是否是重复元素中最后一个元素，若不是则调整
    while(ans<R && left_area==sum(ans+1)) ++ans;

    printf("%lld",ans);
    return 0;
}
